package LeetCode.LC147;

/**
 * @author corn
 * @create 2020-11-08-19:48
 */
public class Solution {
    public ListNode insertionSortList(ListNode head) {
        if(head == null || head.next ==null){
            return head;
        }
        ListNode pro = head,post = head.next;

        ListNode precursor = new ListNode(0);
        precursor.next = head;
        while(pro.next != null){
            if(post.val >= pro.val){
                pro = post;
                post = post.next;
            }else{
                ListNode node = precursor;
                while(node.next != post && node.next.val <= post.val){
                    node = node.next;
                }
                pro.next = post.next;
                post.next = node.next;
                node.next = post;
                post = pro.next;
            }
        }
        return precursor.next;
    }
}
class ListNode {
     int val;
     ListNode next;
     ListNode(int x) { val = x; }
}